/*
 * @lc app=leetcode.cn id=1005 lang=javascript
 *
 * [1005] K 次取反后最大化的数组和
 */

// @lc code=start
/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
var largestSumAfterKNegations = function(A, K) {
    
    A.sort((a,b)=>a-b)
    let arr=A.filter((item)=>item<=0)
    let sum=A.reduce((a,b)=>a+b)
    if(arr.length==0){
        if(K%2==0)return sum
        else return sum-2*A[0]
    }
    if(K>arr.length){
        for(let i=0;i<arr.length;i++){
            sum-=2*arr[i]
        }
        if((K-arr.length)%2==0)return sum
        else return sum-2*Math.min(-arr[arr.length-1],A[arr.length])
    }else{
        for(let i=0;i<K;i++){
            sum-=2*arr[i]
        }
        return sum
    }

};
//第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
// 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
// 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
// 第四步：求和

// @lc code=end

largestSumAfterKNegations([8,-7,-3,-9,1,9,-6,-9,3],8)
console.log(largestSumAfterKNegations([8,-7,-3,-9,1,9,-6,-9,3],8))